/*****************************************************************************
 *   Copyright 2011 ZHUANG Yuan              	                             *
 *   SudokuITS as Final Year Project for BScCS, City University of Hong Kong *
 *                                      									 *
 *   Licensed under the Apache License, Version 2.0 (the "License");         *
 *   you may not use this file except in compliance with the License.        *
 *   You may obtain a copy of the License at                                 *
 *                                                                           *
 *   http://www.apache.org/licenses/LICENSE-2.0                              *
 *                                                                           *
 *   Unless required by applicable law or agreed to in writing, software     *
 *   distributed under the License is distributed on an "AS IS" BASIS,       *
 *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.*
 *   See the License for the specific language governing permissions and     *
 *   limitations under the License.                                          *
 *****************************************************************************/

package android.sudoku.its.expert;

import java.util.ArrayList;
import java.util.List;

import android.sudoku.its.util.GameVariables;

public class Strategies {
	public static final int FULL_HOUSE_COUNT = 8;
	public static final int NAKED_SINGLE_COUNT = 8;
	private StrategiesUtil strategiesUtil;
	
	public Strategies() {
		strategiesUtil = new StrategiesUtil();
	}

	/**
	 * Determine if full house strategy is applicable to a target cell
	 * @param clues			A 2D array of current clues on the game board
	 * @param rowIndex		Row index of the target cell
	 * @param colIndex		Column index of the target cell
	 * @return				A boolean value indicating if full house strategy is applicable to the target cell
	 */
	protected boolean isFullHouseApplicable(int[][] clues, int rowIndex, int colIndex) {
		boolean isFullHouseApplicable = false;
		
		// Check the row containing the target cell
		int count = 0; // count the number of determined cells in this row
		for (int col = 0; col < GameVariables.HOUSE_SIZE; col++) {
			if (clues[rowIndex][col] != 0) // if this is a determined cell
				count ++;
			
			if (count == FULL_HOUSE_COUNT)  // if there is 8 determined cells for this row, full house is applicable
				return isFullHouseApplicable = true;		
		}
		
		// Check the column containing the target cell
		count = 0; // count the number of determined cells in this row
		for (int row = 0; row < GameVariables.HOUSE_SIZE; row++) {
			if (clues[row][colIndex] != 0) //if this is a determined cell
				count ++;
			
			if (count == FULL_HOUSE_COUNT)  // if there is 8 determined cells for this row, full house is applicable
				return isFullHouseApplicable = true;	
		}
		
		// Check the block containing the target cell
		int blockStartRowIndex = (rowIndex/GameVariables.BLOCK_SIDE_LENGTH)*GameVariables.BLOCK_SIDE_LENGTH;
		int blockStartColIndex = (colIndex/GameVariables.BLOCK_SIDE_LENGTH)*GameVariables.BLOCK_SIDE_LENGTH;
		count = 0; // count the number of determined cells in this row

		for (int row=blockStartRowIndex; row<(blockStartRowIndex + GameVariables.BLOCK_SIDE_LENGTH); row++) 
			for (int col=blockStartColIndex; col<(blockStartColIndex + GameVariables.BLOCK_SIDE_LENGTH); col++) 
				if (clues[row][col] != 0) 
					count ++;	
	
		if (count == FULL_HOUSE_COUNT)  // if there is 8 determined cells for this row, full house is applicable
			return isFullHouseApplicable = true;	
		
		// Full house is not applicable
		return isFullHouseApplicable;
		
	}

	/**
	 * Determine if naked single strategy is applicable to a target cell
	 * @param clues			A 2D array of current clues on the game board
	 * @param rowIndex		Row index of the target cell
	 * @param colIndex		Column index of the target cell
	 * @return				A boolean value indicating if naked single strategy is applicable to the target cell
	 */
	protected boolean isNakedSingleApplicable(int[][] clues, int rowIndex, int colIndex) {
		boolean isNakedSinglepplicable = false;
		List<Integer> existingClues = new ArrayList<Integer>(); // store existing clues in the three houses of the target cell
		
		// Check the row containing the target cell
		for (int col = 0; col < GameVariables.HOUSE_SIZE; col++) {
			if (clues[rowIndex][col] != 0) { // if this is a determined cell
				int clueValue = clues[rowIndex][col];
				if (!existingClues.contains(clueValue)) // if the existingClue arraylist does not contain this clue, add its value into the arraylist 
					existingClues.add(clueValue);
			}
		}
		
		// Check the column containing the target cell
		for (int row = 0; row < GameVariables.HOUSE_SIZE; row++) {
			if (clues[row][colIndex] != 0) { // if this is a determined cell
				int clueValue = clues[row][colIndex];
				if (!existingClues.contains(clueValue)) // if the existingClue arraylist does not contain this clue, add its value into the arraylist
					existingClues.add(clueValue);
			}
		}
		
		// Check the block containing the target cell
		int blockStartRowIndex = (rowIndex/GameVariables.BLOCK_SIDE_LENGTH)*GameVariables.BLOCK_SIDE_LENGTH;
		int blockStartColIndex = (colIndex/GameVariables.BLOCK_SIDE_LENGTH)*GameVariables.BLOCK_SIDE_LENGTH;
		
		for (int row=blockStartRowIndex; row<(blockStartRowIndex + GameVariables.BLOCK_SIDE_LENGTH); row++) 
			for (int col=blockStartColIndex; col<(blockStartColIndex + GameVariables.BLOCK_SIDE_LENGTH); col++) 
				if (clues[row][col] != 0) {// if this is a determined cell
					int clueValue = clues[row][col];
					if (!existingClues.contains(clueValue)) // if the existingClue arraylist does not contain this clue, add its value into the arraylist
						existingClues.add(clueValue);
				}
		
		// Check how many distinct clues exist in the three houses of the target cell
		if (existingClues.size() == NAKED_SINGLE_COUNT) // if there is 8 distinct clues, naked single is applicable
			isNakedSinglepplicable = true;
		
		return isNakedSinglepplicable;
	}
	
	/**
	 * Determine if hidden single strategy is applicable to a target cell
	 * @param clues			A 2D array of current clues on the game board
	 * @param rowIndex		Row index of the target cell
	 * @param colIndex		Column index of the target cell
	 * @return				A boolean value indicating if hidden single strategy is applicable to the target cell
	 */
	protected int isHiddenSingleApplicable(List<List<Integer>> cm, int rowIndex, int colIndex) {
		int hiddenSingle = 0; // meaning that there's no cell that can apply Hidden Single
		
		List<Integer> candidateOfTargetCell = new ArrayList<Integer>();
		// Make a copy of the target cell from Candidate Matrix
		candidateOfTargetCell = cm.get(rowIndex * GameVariables.HOUSE_SIZE + colIndex);
				
		/** Check the row containing the target cell **/
		int candidateRow = strategiesUtil.isHiddenSingleApplicableFunc(cm, candidateOfTargetCell, GameVariables.ROW, rowIndex);
		if (candidateRow != 0)
			return hiddenSingle = candidateRow;
	    
		/** Check the column containing the target cell **/
		int candidateCol = strategiesUtil.isHiddenSingleApplicableFunc(cm, candidateOfTargetCell, GameVariables.COLUMN, colIndex);
		if (candidateCol != 0)
			return hiddenSingle = candidateCol;     
	    
		/** Check the block containing the target cell **/
	    int blockIndex = rowIndex/GameVariables.BLOCK_SIDE_LENGTH * GameVariables.BLOCK_SIDE_LENGTH + colIndex/GameVariables.BLOCK_SIDE_LENGTH;
	    int candidateBlock = strategiesUtil.isHiddenSingleApplicableFunc(cm, candidateOfTargetCell, GameVariables.BLOCK, blockIndex);
		if (candidateBlock != 0)
			return hiddenSingle = candidateBlock;     

		return hiddenSingle;
	}

	/**
	 * Determine if naked pair strategy is applicable to a target cell
	 * @param clues			A 2D array of current clues on the game board
	 * @param rowIndex		Row index of the target cell
	 * @param colIndex		Column index of the target cell
	 * @return				A boolean value indicating if naked pair strategy is applicable to the target cell
	 */
	protected boolean isNakedPairApplicable(List<List<Integer>> cm, int rowIndex, int colIndex) {
		boolean isNakedPairApplicable = false;
		List<Integer> candidateOfTargetCell = new ArrayList<Integer>();
		// Make a copy of the target cell from Candidate Matrix
		candidateOfTargetCell = cm.get(rowIndex * GameVariables.HOUSE_SIZE + colIndex);
		
		/** Check the row containing the target cell **/
		// Make a copy the target row from the Candidate Matrix 
		List<List<Integer>> tmpCMRow = new ArrayList<List<Integer>>();
		for (int col = 0; col < GameVariables.HOUSE_SIZE; col++) 
			tmpCMRow.add(cm.get(rowIndex * GameVariables.HOUSE_SIZE + col));
		// Check if the rest of the list contains an element which is equal to the element containing target cell's candidate
		if(isThisElementExistInList(candidateOfTargetCell, tmpCMRow, colIndex)) {
			return isNakedPairApplicable = true;
		}	

		/** Check the column containing the target cell **/
		// Make a copy of the target column from the Candidate Matrix
		List<List<Integer>> tmpCMCol = new ArrayList<List<Integer>>();
		for (int row = 0; row < GameVariables.HOUSE_SIZE; row++) 
			tmpCMCol.add(cm.get(row * GameVariables.HOUSE_SIZE + colIndex));
		// Check if the rest of the list contains an element which is equal to the element containing target cell's candidate
		if(isThisElementExistInList(candidateOfTargetCell, tmpCMCol, rowIndex)) {
			return isNakedPairApplicable = true;
		}
		
		/** Check the block containing the target cell **/
		// Make a copy of the target block from the Candidate Matrix
		List<List<Integer>> tmpCMBlock = new ArrayList<List<Integer>>();
		int blockStartRowIndex = (rowIndex/GameVariables.BLOCK_SIDE_LENGTH)*GameVariables.BLOCK_SIDE_LENGTH;
		int blockStartColIndex = (colIndex/GameVariables.BLOCK_SIDE_LENGTH)*GameVariables.BLOCK_SIDE_LENGTH;
		for (int row = 0; row < GameVariables.BLOCK_SIDE_LENGTH; row++) {
			for (int col = 0; col < GameVariables.BLOCK_SIDE_LENGTH; col++) {
				int cmIndex = (row + blockStartRowIndex) * GameVariables.HOUSE_SIZE + (col + blockStartColIndex);
				tmpCMBlock.add(cm.get(cmIndex));
			}
		}
		// Calculate the index of target cell in the copied Candidate Matrix for the target block
		int tmpCMBlockIndex = (rowIndex - blockStartRowIndex) * GameVariables.BLOCK_SIDE_LENGTH + (colIndex - blockStartColIndex);
		// Check if the rest of the list contains an element which is equal to the element containing target cell's candidate		
		if(isThisElementExistInList(candidateOfTargetCell, tmpCMBlock, tmpCMBlockIndex)) {
			return isNakedPairApplicable = true;
		}

		return isNakedPairApplicable;
	}

	/**
	 * Update the Applicable Strategy Matrix for Hidden Pair strategy
	 * @param cm		Candidate Matrix which contains candidates for each cell
	 * @param asm		Applicable Strategy Matrix which contains applicable strategies for each cell
	 * @return			An updated Applicable Strategy Matrix
	 */
	protected List<List<Integer>> updateASMForHiddenPair(List<List<Integer>> cm, List<List<Integer>> asm) {		
		// Check each row
		asm = strategiesUtil.updateASMForHiddenPairByHouse(cm, asm, GameVariables.ROW);
		
		// Check column
		asm = strategiesUtil.updateASMForHiddenPairByHouse(cm, asm, GameVariables.COLUMN);
		
		// Check block
		asm = strategiesUtil.updateASMForHiddenPairByHouse(cm, asm, GameVariables.BLOCK);
	
		return asm;
	}	
	
	/**
	 * Check if the rest of a list of list called A after removing an element still contains another list B
	 * @param element				A list called B
	 * @param list					A list of List called A 
	 * @param targetCellIndex		The index of the element to be removed
	 * @return						A boolean value indicating if A contains B after element removal
	 */
	private boolean isThisElementExistInList(List<Integer> element, List<List<Integer>> list, int targetCellIndex) {
		boolean isThisElementExistInList = false;
		
		// Remove the element containing target cell's candidate
		list.remove(targetCellIndex);
		// Check if the rest of the list contains an element which is equal to the element containing target cell's candidate
		if (list.contains(element))
			isThisElementExistInList = true;
		
		return isThisElementExistInList;
	}	
}
